<?php

class Node
{
    public $value;
    public $child_left;
    public $child_right;
}

$a = new Node();
$b = new Node();
$c = new Node();
$d = new Node();
$e = new Node();
$f = new Node();
$g = new Node();
$h = new Node();
$i = new Node();

$a->value = '1';

$b->value = '2';
$c->value = '3';

$d->value = '4';
$e->value = '5';

$f->value = '6';
$g->value = '7';


$a->child_left = $b;
$a->child_right = $c;

//   2
// 4  5

$b->child_left = $d;
$b->child_right = $e;


//   3
//  6   7

$c->child_left = $f;
$c->child_right = $g;

bfs($a);

echo PHP_EOL;

//dfs($a);


function bfs($root)
{
    $queue = [ $root];
    while (count($queue)) {

        for ($i = 0; $i < count($queue); $i++) {

            $top = array_shift($queue);
            echo $top->value, PHP_EOL;

            if ($top->child_left) {
                array_push($queue, $top->child_left);
            }

            if ($top->child_right) {
                array_push($queue, $top->child_right);
            }
        }
    }
}



//       1
//    2     3
// 4  5    6  7

function dfs($root)
{
    $queue = [$root];
    while (count($queue)) {
        for ($i = 0; $i < count($queue); $i++) {

            $top = array_pop($queue);
            echo $top->value, PHP_EOL;

            if ($top->child_left) {
                array_push($queue, $top->child_left);
            }

            if ($top->child_right) {
                array_push($queue, $top->child_right);
            }
        }
    }
}






